#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

class Solution {
	int size = 0;
	vector<int> rank;
	map<int, int> lmp;
	vector<int> imax;
	vector<int> change;
	vector<bool> update;

	void build(int l, int r, int i)
	{
		if (l == r) {
			imax[i] = 0;
		} else {
			int mid = (l + r) >> 1;
			build(l, mid, i << 1);
			build(mid + 1, r, i << 1 | 1);
		}
		up(i);
	}

	void lazy(int i, int v)
	{
		imax[i] = v;
		change[i] = v;
		update[i] = true;
	}

	void up(int i)
	{
		imax[i] = max(imax[i << 1], imax[i << 1 | 1]);
	}

	void down(int i)
	{
		if (update[i]) {
			lazy(i << 1, change[i]);
			lazy(i << 1 | 1, change[i]);
			update[i] = 0;
		}
	}

	void reset(int jobl, int jobr, int v, int l, int r, int i)
	{
		if (jobl <= l && r <= jobr) {
			lazy(i, v);
			return;
		}
		down(i);

		int mid = (l + r) >> 1;
		if (jobl <= mid) {
			reset(jobl, jobr, v, l, mid, i << 1);
		}
		if (mid < jobr) {
			reset(jobl, jobr, v, mid + 1, r, i << 1 | 1);
		}

		up(i);
	}

	int query(int jobl, int jobr, int l, int r, int i)
	{
		if(jobl <= l && r <= jobr){
			return imax[i];
		}
		down(i);

		int ans = 0;
		int mid = (l + r) >> 1;
		if(jobl <= mid){
			ans = max(ans, query(jobl, jobr, l, mid, i << 1));
		}
		if(mid < jobr){
			ans = max(ans, query(jobl, jobr, mid + 1, r, i << 1 | 1));
		}

		return ans;
	}

	void prepare(vector<vector<int>> &positions)
	{
		size = positions.size();
		rank.resize(size << 1, 0);
		for (int i = 0, pos = 0; i < size; i++) {
			rank[pos++] = positions[i][0];
			rank[pos++] = positions[i][0] + positions[i][1] - 1;
		}
		sort(rank.begin(), rank.end());
		rank.erase(unique(rank.begin(), rank.end()), rank.end());
		int id = 1;
		for (auto v : rank) {
			lmp[v] = id++;
		}

		size = rank.size();
		change.resize(size << 2, 0);
		update.resize(size << 2, false);
		imax.resize(size << 2, 0);
	}

    public:
	vector<int> fallingSquares(vector<vector<int>> &positions)
	{
		prepare(positions);
		vector<int> ans;
		int hmax = 0;
		for(int i = 0, l = 0, r = 0, h = 0; i < positions.size(); i++){
			l = positions[i][0];
			h = positions[i][1];
			r = l + h - 1;
			l = lmp[l];
			r = lmp[r];
			h = query(l, r, 1, size, 1) + h;
			hmax = max(hmax, h);
			ans.push_back(hmax);
			reset(l, r, h, 1, size, 1);
		}
		return ans;
	}
};

int main()
{
	vector<vector<int>> positions = { { 9, 7 }, { 1, 9 }, { 3, 1 } };
	vector<int> ans = Solution().fallingSquares(positions);
	for (auto v : ans) {
		cout << v << " ";
	}
	cout << endl;
	return 0;
}